---
title: "L2-048 寻宝图"
created: 2025-11-28
tags:
  - 算法
---

# L2-048 寻宝图

## 题目 [L2-048 寻宝图](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=1649748772841508875&page=1)

![[image-69ee975f.png]]

## 思路分析

洪水灌溉

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

//const int N=1010,M=1010;
vector<vector<char>> g;
vector<vector<bool>> st;
//char g[N][M];
//bool st[N][M];
int n,m;
int res=0,res2=0;

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];
}
void dfs(int x,int y,bool& havebz){

	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
        if(isVaild(nx,ny) && g[nx][ny]!='0'){
            if(g[nx][ny]!='1') havebz=true;
            st[nx][ny]=true;
			dfs(nx,ny,havebz);
        }
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;
    g.resize(n,vector<char> (m));
    st.resize(n,vector<bool> (m,false));
	for(int i=0;i<n;i++){
        string s;cin>>s;
        for(int j=0;j<m;j++){
            g[i][j]=s[j];
        }
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]!='0' && !st[i][j]){
                bool havebz=false;
                if(g[i][j]!='1')
                    havebz=true;
				st[i][j]=true;
				dfs(i,j,havebz);
				res++;
                if(havebz) res2++;
			}
		}
	}
	cout<<res<<" "<<res2<<endl;

	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-047 锦标赛|L2-047 锦标赛]] 🏠 [[00-天梯赛]] ➡️ [[L2-049 鱼与熊掌|L2-049 鱼与熊掌]]